package wh.二进制求和;

import java.util.Arrays;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/4/10 21:10
 * @description:给你两个二进制字符串，返回它们的和（用二进制表示）
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        String a = "111";
        String b = "10";
        System.out.println(addBinary2(a, b));
    }

    public static String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder builder = new StringBuilder();
        //循环相加两个字符串相同长度的低位数部分
        while (i >= 0 && j >= 0) {
            int sum = carry;
            // - '0' 这个操作是为了将char类型自动转为int型
            sum += a.charAt(i--) - '0';
            sum += b.charAt(j--) - '0';
            //carry表示进位数字,如果sum大于等于2，则carry为1，否则carry为0
            carry = sum / 2;
            //如果sum为2,那么追加1，否则为0
            builder.append(sum % 2);
        }
        // 如果 a 还没遍历完成（a串比b串长），则继续遍历添加 a 的剩余部分
        while (i >= 0) {
            int sum = carry + a.charAt(i--) - '0';
            carry = sum / 2;
            builder.append(sum % 2);
        }
        // 如果 b 还没遍历完成（b串比a串长），则继续遍历添加 b 的剩余部分
        while (j >= 0) {
            int sum = carry + b.charAt(j--) - '0';
            carry = sum / 2;
            builder.append(sum % 2);
        }
        //如果 carry 不等于0 还有个进位数没加进去，需要补充
        if (carry == 1) {
            builder.append(carry);
        }
        //反转字符串获得正常结果
        return builder.reverse().toString();

        //简化处理,核心思想不变
      /*  while (i >= 0 || j >= 0) {
            if (i >= 0) carry += a.charAt(i--) - '0';
            if (j >= 0) carry += b.charAt(j--) - '0';
            builder.append(carry % 2);
            carry /=  2;
        }
        if (carry == 1) {
            builder.append(carry);
        }*/
    }

    //解法2整体思路是将两个字符串较短的用 00 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。
    public static String addBinary2(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            sum += (i >= 0 ? a.charAt(i) - '0' : 0);
            sum += (j >= 0 ? b.charAt(j) - '0' : 0);
            ans.append(sum % 2);
            ca = sum / 2;
        }
        ans.append(ca == 1 ? ca : "");
        //最后如果有进位，则在前方进行字符串拼接添加进位

        return ans.reverse().toString();
    }

}
